package org.example.binaryTree;

public class TestBST {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int data) {

            this.value = data;
        }
    }
    /**
     * 检查是否为搜索二叉树
     */
    public static int preValue = Integer.MIN_VALUE;
    public static boolean checkBST(Node head) {
        if (head == null) {
            return  true;
        }
        boolean isLeftBst = checkBST(head.left);
        if (!isLeftBst) {
            return false;
        }
        if(head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        return checkBST(head.right);
    }

    //套路写法

    /**
     * 返会的信息  子树是否为二叉搜索树 最大值 最小值
     */
    public static class ReturnType{
        public boolean isBST;
        public int max;
        public int min;

        public ReturnType(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }
    public static ReturnType process(Node x) {
        if (x == null) {
            return new ReturnType(true,0,0);
        }
        ReturnType leftData = process(x.left);
        ReturnType rightData = process(x.right);

        int max = x.value;
        int min = x.value;
        if(leftData != null) {
            max = Math.max(leftData.max, max);
            min = Math.min(leftData.min, min);
        }
        if(rightData != null) {
            max = Math.max(rightData.max, max);
            min = Math.min(rightData.min, min);
        }
        boolean isBST = true;
        if(leftData != null && (!leftData.isBST || leftData.max > x.value)) {
            isBST = false;
        }
        if(rightData != null && (!rightData.isBST || rightData.min < x.value)) {
            isBST = false;
        }
        return new ReturnType(isBST,max,min);
    }
}
